using System;
using System.Collections.Generic;
using UnityEngine;

namespace Gj.Pathfinding
{
    public class BLJPSGrid : JPSGrid
    {
        private Dictionary<int, List<int>> xBoundaryPoints;
        private Dictionary<int, List<int>> yBoundaryPoints;

        public BLJPSGrid(int[,] navigable) : base(navigable)
        {
            preProcessGrid();
        }

        private void flushReProcess(Vector2Int node)
        {
            for (var y = 0; y < BoundsMaxY; y++)
                if (xBoundaryPoints[y].Count == 0)
                {
                    var currentPassable = false;
                    xBoundaryPoints[y].Clear();
                    for (var x = 0; x < BoundsMaxX; x++)
                        if (_N(x, y, 0) != currentPassable)
                        {
                            xBoundaryPoints[y].Add(x);
                            currentPassable = !currentPassable;
                        }

                    //if (currentPassable)
                    xBoundaryPoints[y].Add(BoundsMaxX);
                }

            for (var x = 0; x < BoundsMaxX; x++)
                if (yBoundaryPoints[x].Count == 0)
                {
                    var currentPassable = false;
                    yBoundaryPoints[x].Clear();

                    for (var y = 0; y < BoundsMaxY; y++)
                        if (_N(x, y, 0) != currentPassable)
                        {
                            yBoundaryPoints[x].Add(y);
                            currentPassable = !currentPassable;
                        }

                    //if (currentPassable)
                    yBoundaryPoints[x].Add(BoundsMaxX);
                }
        }

        private void preProcessGrid()
        {
            for (var y = 0; y < BoundsMaxY; y++)
            {
                var currentPassable = false;
                xBoundaryPoints.Add(y, new List<int>());
                for (var x = 0; x < BoundsMaxX; x++)
                    if (_N(x, y, 0) != currentPassable)
                    {
                        xBoundaryPoints[y].Add(x);
                        currentPassable = !currentPassable;
                    }

                //if (currentPassable)
                xBoundaryPoints[y].Add(BoundsMaxX);
            }

            for (var x = 0; x < BoundsMaxX; x++)
            {
                var currentPassable = false;
                yBoundaryPoints.Add(x, new List<int>());
                for (var y = 0; y < BoundsMaxX; y++)
                    if (_N(x, y, 0) != currentPassable)
                    {
                        yBoundaryPoints[x].Add(y);
                        currentPassable = !currentPassable;
                    }

                //if (currentPassable)
                yBoundaryPoints[x].Add(BoundsMaxY);
            }
        }

        private int binarySearch(List<int> v, int val)
        {
            var l = 0;
            var r = v.Count - 1;
            var index = r / 2;
            while (true)
            {
                if (v[index] <= val && v[index + 1] > val)
                    return index;
                if (v[index] > val)
                    r = index - 1;
                else
                    l = index + 1;

                index = l + (r - l) / 2;
            }

            return -1;
        }

        private Vector2Int getEastEndPoshortReOpen(int x, int y)
        {
            if (y < BoundsMinY || y >= BoundsMaxY)
                return new Vector2Int(BoundsMaxX, BoundsMaxX);

            if (xBoundaryPoints[y][0] > x)
                return new Vector2Int(xBoundaryPoints[y][0], xBoundaryPoints[y][0]);

            var i = binarySearch(xBoundaryPoints[y], x);
            if (i % 2 > 0)
                return new Vector2Int(xBoundaryPoints[y][i + 1], xBoundaryPoints[y][i + 1]);
            return new Vector2Int(xBoundaryPoints[y][i + 1] - 1,
                i + 2 < xBoundaryPoints[y].Count ? xBoundaryPoints[y][i + 2] : BoundsMaxX);
        }

        private Vector2Int getWestEndPoshortReOpen(int x, int y)
        {
            if (y < BoundsMinY || y >= BoundsMaxY)
                return new Vector2Int(-1, -1);

            if (xBoundaryPoints[y][0] > x)
                return new Vector2Int(-1, -1);

            var i = binarySearch(xBoundaryPoints[y], x);
            if (i % 2 > 0)
                return new Vector2Int(xBoundaryPoints[y][i] - 1, xBoundaryPoints[y][i] - 1);
            return new Vector2Int(xBoundaryPoints[y][i], i - 1 < 0 ? -1 : xBoundaryPoints[y][i - 1] - 1);
        }

        private Vector2Int getSouthEndPoshortReOpen(int x, int y)
        {
            if (x < BoundsMinX || x >= BoundsMaxX)
                return new Vector2Int(BoundsMaxY, BoundsMaxY);

            if (yBoundaryPoints[x][0] > y)
                return new Vector2Int(yBoundaryPoints[x][0], yBoundaryPoints[x][0]);

            var i = binarySearch(yBoundaryPoints[x], y);
            if (i % 2 > 0)
                return new Vector2Int(yBoundaryPoints[x][i + 1], yBoundaryPoints[x][i + 1]);
            return new Vector2Int(yBoundaryPoints[x][i + 1] - 1,
                i + 2 < yBoundaryPoints[x].Count ? yBoundaryPoints[x][i + 2] : BoundsMaxY);
        }

        private Vector2Int getNorthEndPointReOpen(int x, int y)
        {
            if (x < BoundsMinX || x >= BoundsMaxX)
                return new Vector2Int(-1, -1);

            if (yBoundaryPoints[x][0] > y)
                return new Vector2Int(-1, -1);

            var i = binarySearch(yBoundaryPoints[x], y);
            if (i % 2 > 0)
                return new Vector2Int(yBoundaryPoints[x][i] - 1, yBoundaryPoints[x][i] - 1);
            return new Vector2Int(yBoundaryPoints[x][i], i - 1 < 0 ? -1 : yBoundaryPoints[x][i - 1] - 1);
        }

        public bool GetJumpPoint(JPS jps, JPSNode node, Vector2Int goal, byte dir, int mask, out JPSNode jp)
        {
            node = jps.NextNode(node, dir);
            jp = default;
            if (!_N(node.Location.x, node.Location.y, mask))
                return false;
            var ret = false;
            Vector2Int up, center, down;
            switch (dir)
            {
                case 1: //North
                    up = getNorthEndPointReOpen(node.Location.x - 1, node.Location.y);
                    center = getNorthEndPointReOpen(node.Location.x, node.Location.y);
                    down = getNorthEndPointReOpen(node.Location.x + 1, node.Location.y);

                    if (node.Location.x == goal.x && node.Location.y >= goal.y && center.x <= goal.y)
                    {
                        jp = jps.NewNode(goal.x, goal.y, dir);
                        return true;
                    }

                    if (down.x != -1 && ((down.y > -1 && down.x > center.x && down.y + 2 > center.x) ||
                                         (down.x == down.y && down.x + 2 > center.x)))
                    {
                        jp = jps.NewNode(node.Location.x, down.y + 1, dir);
                        ret = true;
                    }

                    if (up.x != -1 && ((up.y > -1 && up.x > center.x && up.y + 2 > center.x) ||
                                       (up.x == up.y && up.x + 2 > center.x)))
                    {
                        jp = jps.NewNode(node.Location.x, ret ? Math.Max(jp.Location.y, up.y + 1) : up.y + 1, dir);
                        return true;
                    }

                    return ret;
                case 3: //EAST
                    up = getEastEndPoshortReOpen(node.Location.x, node.Location.y - 1);
                    center = getEastEndPoshortReOpen(node.Location.x, node.Location.y);
                    down = getEastEndPoshortReOpen(node.Location.x, node.Location.y + 1);

                    if (node.Location.y == goal.y && node.Location.x <= goal.x && center.x >= goal.x)
                    {
                        jp = jps.NewNode(goal.x, goal.y, dir);
                        return true;
                    }

                    if (down.x != BoundsMaxX && ((down.y < BoundsMaxX && down.x < center.x && down.y - 2 < center.x) ||
                                                 (down.x == down.y && down.x - 2 < center.x)))
                    {
                        jp = jps.NewNode(down.y - 1, node.Location.y, dir);
                        ret = true;
                    }

                    if (up.x != BoundsMaxX && ((up.y < BoundsMaxX && up.x < center.x && up.y - 2 < center.x) ||
                                               (up.x == up.y && up.x - 2 < center.x)))
                    {
                        jp = jps.NewNode(ret ? Math.Min(jp.Location.x, up.y - 1) : up.y - 1, node.Location.y, dir);
                        return true;
                    }

                    return ret;
                case 5: //SOUTH
                    up = getSouthEndPoshortReOpen(node.Location.x - 1, node.Location.y);
                    center = getSouthEndPoshortReOpen(node.Location.x, node.Location.y);
                    down = getSouthEndPoshortReOpen(node.Location.x + 1, node.Location.y);

                    if (node.Location.x == goal.x && node.Location.y <= goal.y && center.x >= goal.y)
                    {
                        jp = jps.NewNode(goal.x, goal.y, dir);
                        return true;
                    }

                    if (down.x != BoundsMaxY && ((down.y < BoundsMaxY && down.x < center.x && down.y - 2 < center.x) ||
                                                 (down.x == down.y && down.x - 2 < center.x)))
                    {
                        jp = jps.NewNode(node.Location.x, down.y - 1, dir);
                        ret = true;
                    }

                    if (up.x != BoundsMaxY && ((up.y < BoundsMaxY && up.x < center.x && up.y - 2 < center.x) ||
                                               (up.x == up.y && up.x - 2 < center.x)))
                    {
                        jp = jps.NewNode(node.Location.x, ret ? Math.Min(jp.Location.y, up.y - 1) : up.y - 1, dir);
                        return true;
                    }

                    return ret;
                case 7: //WEST
                    up = getWestEndPoshortReOpen(node.Location.x, node.Location.y - 1);
                    center = getWestEndPoshortReOpen(node.Location.x, node.Location.y);
                    down = getWestEndPoshortReOpen(node.Location.x, node.Location.y + 1);

                    if (node.Location.y == goal.y && node.Location.x >= goal.x && center.x <= goal.x)
                    {
                        jp = jps.NewNode(goal.x, goal.y, dir);
                        return true;
                    }

                    if (down.x != -1 && ((down.y > -1 && down.x > center.x && down.y + 2 > center.x) ||
                                         (down.x == down.y && down.x + 2 > center.x)))
                    {
                        jp = jps.NewNode(down.y + 1, node.Location.y, dir);
                        ret = true;
                    }

                    if (up.x != -1 && ((up.y > -1 && up.x > center.x && up.y + 2 > center.x) ||
                                       (up.x == up.y && up.x + 2 > center.x)))
                    {
                        jp = jps.NewNode(ret ? Math.Max(jp.Location.x, up.y + 1) : up.y + 1, node.Location.y, dir);
                        return true;
                    }

                    return ret;
            }

            return false;
        }
    }
}